package com.lw.leetcode.stack.c;

import com.lw.test.util.Utils;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * stack
 * 2454. 下一个更大元素 IV
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/31 14:20
 */
public class SecondGreaterElement {

    public static void main(String[] args) {
        SecondGreaterElement test = new SecondGreaterElement();

        // [9,6,6,-1,-1]
//        int[] arr = {2, 4, 0, 9, 6};

        // [-1,-1]
//        int[] arr = {3, 3};

        // [79447884,89104770,-1,64586136,64586136,64706972,89104770,89104770,89104770,-1,-1]
//        int[] arr = {16749549, 76922525, 79447884, 21032790, 15208294, 46178258, 64586136, 19496767, 18777887, 64706972, 89104770};

        //
        int[] arr = Utils.getArr(100000, 0, 1000000000);

        int[] ints = test.secondGreaterElement(arr);
//        System.out.println(Arrays.toString(ints));
    }

    public int[] secondGreaterElement(int[] nums) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int length = nums.length;
        int[] vs = new int[length];
        int[] is = new int[length];
        int vi = -1;
        for (int i = length - 1; i >= 0; i--) {
            int num = nums[i];
            while (vi != -1) {
                if (vs[vi] > num) {
                    break;
                }
                vi--;
            }
            if (vi != -1) {
                map.computeIfAbsent(is[vi], v -> new ArrayList<>()).add(i);
            }
            vi++;
            vs[vi] = num;
            is[vi] = i;
        }
        vi = -1;
        Arrays.fill(is, -1);
        for (int i = length - 1; i >= 0; i--) {
            int num = nums[i];
            List<Integer> list = map.get(i);
            if (list != null) {
                for (int index : list) {
                    is[index] = find(vs, vi, nums[index]);
                }
            }
            while (vi != -1) {
                if (vs[vi] > num) {
                    break;
                }
                vi--;
            }
            vi++;
            vs[vi] = num;
        }
        return is;
    }

    private int find(int[] arr, int end, int t) {
        if (t >= arr[0] || end < 0) {
            return -1;
        }
        int st = 0;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (arr[m] <= t) {
                end = m - 1;
            } else {
                st = m;
            }
        }
        return arr[st];
    }


}
